#include<stdio.h>
int mp_simple(int a,int n){
    int res=1;
    int i=0;
    for(i=0;i<n;i++)
        res*=a;
    return res%1000;
}
int mp(int a,int n){
    a%=1000;
    if(a==1||n==0)
        return 1;
    if(a==0||n==1)
        return a;
    if(n%2==0)
        return mp(a*a,n/2);
    return (mp(a*a,n/2)*a)%1000;
}
int main(){
    mp(10456,23456);
    return 0;
}
